package com.leetBook.Krahets.linkedList;

/**
 * 《图解算法与数据结构》链表第 5 题：给定两个以 有序链表 形式记录的训练计划 l1、l2，分别记录了两套核心肌群训练项目编号，请合并这两个训练计划，按训练项目编号 升序 记录于链表并返回。
 */
public class MergeSortList {
    /**
     * 递归方式
     * @param l1 有序列表1
     * @param l2 有序列表2
     * @return 合并后的幼畜列表
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        if (l1.val <= l2.val){
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    /**
     * 循环/迭代
     * @param l1 有序列表1
     * @param l2 有序列表2
     * @return 合并后的幼畜列表
     */
    public ListNode mergeTwoListsWhile(ListNode l1, ListNode l2){
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode tmp;
        ListNode returnValue = null;

        boolean b = true;
        while (l1 != null && l2 != null){
            if (l1.val <= l2.val){
                tmp = l1;
                tmp.next = l2;

                if (b){
                    returnValue = tmp;
                }

                tmp = tmp.next;
                l1 = l1.next;
            }else {
                tmp = l2;
                tmp.next = l1;

                if (b){
                    returnValue = tmp;
                }

                tmp = tmp.next;
                l2 = l2.next;
            }

            b=false;
        }
        return returnValue;
    }
}
